package pers.qianyu.month_202011.date_20201130;

import java.util.*;

/**
 * [Leetcode 每日一题]
 * 767. 重构字符串
 * https://leetcode-cn.com/problems/reorganize-string/
 *
 * @author mizzle rain
 * @date 2020-11-30 13:14
 */
public class ReorganizeString {
    /**
     * 使用优先队列
     */
    public String reorganizeString(String S) {
        if (S == null || S.length() < 2) {
            return S;
        }
        int[] map = new int[26];
        for (int i = 0; i < S.length(); i++) {
            map[S.charAt(i) - 'a']++;
        }
        // 如果说有一个字符的数量大于 (n + 1) / 2 的话，就直接返回 ""
        int count = (S.length() + 1) >> 1;
        for (int i = 0; i < 26; i++) {
            if (map[i] > count) {
                return "";
            }
        }
        StringBuilder builder = new StringBuilder();
        PriorityQueue<Character> q = new PriorityQueue<>((o1, o2) -> map[o2 - 'a'] - map[o1 - 'a']);
        for (int i = 0; i < 26; i++) {
            if (map[i] > 0) {
                q.offer((char) (i + 'a'));
            }
        }
        while (q.size() > 1) {
            char c1 = q.poll();
            char c2 = q.poll();
            builder.append(c1).append(c2);
            map[c1 - 'a']--;
            map[c2 - 'a']--;
            if (map[c1 - 'a'] > 0) {
                q.offer(c1);
            }
            if (map[c2 - 'a'] > 0) {
                q.offer(c2);
            }
        }
        if (q.size() > 0) {
            builder.append(q.poll());
        }
        return builder.toString();
    }


    public static void main(String[] args) {
        String result = new ReorganizeString().reorganizeString("eqpspvbpppwpgyppppe");
        System.out.println("result = " + result);
    }
}
